package week07

import "math"

// 743. 网络延迟时间
// https://leetcode-cn.com/problems/network-delay-time/

func networkDelayTime(times [][]int, n int, k int) int {
	var dist = make([]int, n+1)
	for i := range dist {
		dist[i] = math.MaxInt32
	}
	dist[k] = 0
	// Bellman-Ford 算法
	// for i := 1; i < n; n++ {
	//     var flag = false
	//     for _, edge := range times {
	//         var x, y, z = edge[0], edge[1], edge[2]
	//         if dist[x] < dist[y] - z {	// 加法可能越界，移项变为减法
	//             dist[y] = dist[x] + z
	//             flag = true
	//         }
	//     }
	//     if !flag {
	//         break
	//     }
	// }
	// Dijkstra 算法  取最小点
	// 构建图  出边，边长
	var graph = make(map[int][]*item)
	for _, edge := range times {
		var x, y, z = edge[0], edge[1], edge[2]
		graph[x] = append(graph[x], &item{z, y})
	}

	var visit = make([]bool, n+1)
	var heap = &BinaryHeap{}
	heap.push(&item{dist[k], k})
	for !heap.empty() {
		top := heap.pop()
		x := top.idx
		if visit[x] {
			continue
		}
		visit[x] = true
		// 遍历所有出边
		for _, edge := range graph[x] {
			var y, z = edge.idx, edge.dist
			if dist[x] < dist[y] - z {	// 加法可能越界，移项变为减法
				dist[y] = dist[x] + z
				heap.push(&item{dist[y], y})
			}
		}
	}

	var ans = 0
	ans = max(ans, dist[1:]...)
	if ans == math.MaxInt32 {
		return -1
	}
	return ans
}

type item struct {
	dist int	// 边长
	idx int	// 端点
}

// 小顶堆
type BinaryHeap struct {
	list []*item
}

func (heap *BinaryHeap) push(val *item) {
	heap.list = append(heap.list, val)
	// 调整堆
	var cur = len(heap.list)-1
	var parent = (cur - 1) / 2
	for parent >= 0 {
		if heap.list[parent].dist > heap.list[cur].dist {
			heap.list[parent], heap.list[cur] = heap.list[cur], heap.list[parent]
			cur = parent
			parent = (cur - 1) / 2
		} else {
			break
		}
	}
}

func (heap *BinaryHeap) pop() *item {
	val := heap.list[0]
	heap.list[0] = heap.list[len(heap.list)-1]
	heap.list = heap.list[:len(heap.list)-1]
	// 调整堆
	var cur = 0
	var child = cur * 2 + 1
	for child < len(heap.list) {
		var other = cur * 2 + 2
		if other < len(heap.list) && heap.list[other].dist < heap.list[child].dist {
			child = other
		}
		if heap.list[cur].dist > heap.list[child].dist {
			heap.list[cur], heap.list[child] = heap.list[child], heap.list[cur]
			cur = child
			child = cur * 2 + 1
		} else {
			break
		}
	}
	return val
}

func (heap *BinaryHeap) empty() bool {
	return len(heap.list) == 0
}

func max(x int, vals ...int) int {
	for _, val := range vals {
		if val > x {
			x = val
		}
	}
	return x
}
